#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
const int N=2e6+10;
int f[N];
typedef pair<int,int> PII;
vector<int> edges[N];

int n,m;
int dist[N];
bool st[N];
priority_queue<PII,vector<PII>,greater<PII>> heap;
void dj()
{
	memset(dist,0x3f,sizeof dist);
	heap.push({0,1});
	dist[1]=0;
	f[1]=1;
	
	while(heap.size())
	{
		auto u=heap.top();
		heap.pop();
		int a=u.second;
		
		if(st[a]) continue;
		st[a]=true;
		
		for(auto b:edges[a])
		{
			if(dist[a]+1<dist[b])
			{
				dist[b]=dist[a]+1;
				f[b]=f[a];
				heap.push({dist[b],b});
			}
			else if(dist[a]+1==dist[b])
			{
				f[b]=(f[a]+f[b])%100003;
			}
		}
	}
} 
//对于这道题来说，bfs和spfa都一样，首先我们的bfs和spfa对于这道题我们都不能用标记数组。

void spfa()
{
	memset(dist,0x3f,sizeof dist);
	queue<int> q;
	q.push(1);
	dist[1]=0;
	f[1]=1;
	while(q.size())
	{
		int u=q.front();
		q.pop();
		
		for(auto t:edges[u])
		{
			if(dist[u]+1<dist[t])
			{
				dist[t]=dist[u]+1;
				f[t]=f[u];
				q.push(t);
			}
			//注意这个地方一定是else if不然的话走完上一个一定会走下一个
			//我真服了，严谨一点 
			else if(dist[u]+1==dist[t])
			{
				f[t]=(f[u]+f[t])%100003;
			}
		}
	}	
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x=0,y=0;
		cin>>x>>y;
		edges[x].push_back(y);
		//无向图，存两次
		edges[y].push_back(x); 
	}
	dj();
	for(int i=1;i<=n;i++)
	{
		printf("%d\n",f[i]);
	}
	return 0;
}